package com.since.data_structure.tree;

import java.util.*;

/**
 * Created by Sincerity on 2020/5/22.
 * 描述：哈夫曼编码
 * 1.得到一个对象的Byte数组
 * 2.通过对象的byte数组去统计每个字节出现的频率{@link #getNodes(byte[])}
 * 3.通过对象数组的字节权重得到这个对象的哈夫曼树{@link #createHuffmanTreeByList(List)}
 * 4.通过哈夫曼树得到对应的哈夫曼编码{@link #getCode(Node)#getCodes(Node, String, StringBuilder)}
 * 5.通过哈夫曼编码和原对象的byte数组得到一个压缩后的哈夫曼压缩数组{@link #zip(byte[], Map)}
 * 6.解压哈夫曼编码表{@link #decode(byte[], Map)}
 */
class HuffmanCode {

    /**
     * 1. 将哈夫曼编码表存放在Map中  Map<Byte, String> 形式 a ==> 100
     * 2.拿到每个字符编码的哈夫曼编码 存储叶子节点的哈夫曼编码
     */
    private static Map<Byte, String> huffmanCodes = new HashMap<>(); //Key =字符 Value =='哈夫曼编码'
    private static StringBuilder stringBuilder = new StringBuilder();//拼接叶子节点的哈弗曼编码

    public static void main(String[] args) {
        String content = "i like like like java do you like a java";
        byte[] bytes = content.getBytes();
        System.out.println(bytes.length);
        List<Node> codes = getNodes(bytes);
        System.out.println(codes);
        System.out.println("创建的哈夫曼树");
        Node huffmanTree = createHuffmanTreeByList(codes);
        System.out.println("前序遍历");
        huffmanTree.preOrder();
        Map<Byte, String> code = getCode(huffmanTree);
        System.out.println("生成的哈夫曼编码-->:" + code);
        byte[] zip = zip(bytes, code);
        byte[] huffmanZipCode = huffmanZip(bytes);
        System.out.println("原数组Code:" + Arrays.toString(bytes));
        System.out.println("哈夫曼Code:" + Arrays.toString(huffmanZipCode));
        byte[] decode = decode(huffmanZipCode, code);
        System.out.println("解码后的数据:" + new String(decode));
    }

    /**
     * 得到哈夫曼的编码表
     *
     * @param bytes 原字符字节数组
     * @return 哈夫曼的编码表 解码的关键
     */
    public static Map<Byte, String> getHuffmanCodes(byte[] bytes) {
        List<Node> codes = getNodes(bytes);
        Node huffmanTree = createHuffmanTreeByList(codes);
        return getCode(huffmanTree);
    }

    /**
     * 对哈夫曼编码进行解码 怎么样压缩的按照反逻辑来解压即可
     *
     * @param huffmanZipCode 哈夫曼编码后的字节数组
     * @param huffmanCodes   哈夫曼的编码表
     * @return 压缩之前的原数组
     */
    public static byte[] decode(byte[] huffmanZipCode, Map<Byte, String> huffmanCodes) {
        //1. 先得到 huffmanBytes 对应的 二进制的字符串 ， 形式 1010100010111...
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < huffmanZipCode.length; i++) {
            byte b = huffmanZipCode[i];
            boolean flag = (i == huffmanZipCode.length - 1);
            stringBuilder.append(byteToBitString(b, !flag));
        }
        //把字符串按照指定的赫夫曼编码进行解码 即key==>编码表中Value value ===> 编码表中的Key
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
        //创建一个集合保存
        List<Byte> list = new ArrayList<>();
        for (int i = 0; i < stringBuilder.length(); ) {
            int count = 1; // 小的计数器
            boolean flag = true;
            Byte b = null;
            while (flag) {
                //递增的取出 key 1 递归增加
                String key = stringBuilder.substring(i, i + count);//i 不动，让count移动，指定匹配到一个字符
                b = map.get(key);
                if (b == null) {//说明没有匹配到
                    count++;
                } else {
                    //匹配到
                    flag = false;
                }
            }
            list.add(b);
            i += count;//i 直接移动到 count
        }
        byte[] b = new byte[list.size()];
        for (int i = 0; i < b.length; i++) {
            b[i] = list.get(i);
        }
        return b;
    }

    /**
     * 将byte专为二进制的字符串
     *
     * @param b    需要转换的字符
     * @param flag 标志是否需要补高位如果是true ，表示需要补高位，如果是false表示不补, 如果是最后一个字节，无需补高位
     * @return 二进制的字符串
     */
    private static String byteToBitString(byte b, boolean flag) {
        //把字节转为integers
        int temp = b;
        //得到字符的二进制字符串
        if (flag) {
            //8位而禁止最大值就是256
            temp |= 256;
        }
        String binaryString = Integer.toBinaryString(temp);
        if (flag) {
            //不是最后一个字符的话截取最后8位
            return binaryString.substring(binaryString.length() - 8);
        } else {
            return binaryString;
        }
    }

    /**
     * 哈夫曼压缩
     *
     * @param bytes 原始对象对应的字符数组
     * @return 返回一个经过哈夫曼编码压缩后的字节数组
     */
    public static byte[] huffmanZip(byte[] bytes) {
        Map<Byte, String> huffmanCodes = getHuffmanCodes(bytes);
        //根据生成的哈夫曼编码压缩得到压缩后的哈夫曼编码字节数组
        return zip(bytes, huffmanCodes);
    }

    /**
     * 通过字符数组生成一个通过Huffman编码压缩后的字节数组 ,返回哈夫曼编码压缩后的Byte数组
     *
     * @param bytes        原始字符串对应的byte数组
     * @param huffmanCodes 生成的huffman编码集合
     * @return 返回经过Huffman编码后的字节数组
     * 举例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
     * 返回的是 字符串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101
     * 111111100110001001010011011100" => 对应的 byte[] huffmanCodeBytes  ，即 8位对应一个 byte,放入到 huffmanCodeBytes
     * huffmanCodeBytes[0] =  10101000(补码) => byte  [推导  10101000=> 10101000 - 1 => 10100111(反码)=> 11011000= -88 ]
     * huffmanCodeBytes[1] = -88
     */
    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //利用哈夫曼编码表将 byte数组转为huffman编码对应的值
        StringBuilder stringBuilder = new StringBuilder();
        //遍历byte数组
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }
        //这里经过循环后的stringBuilder就是要得到的哈夫曼编码 ,然后将哈夫曼编码转为byte数组
        int len = (stringBuilder.length() + 7) / 8;
//        int len; 等价于上述代码
//        if (stringBuilder.length() % 8 == 0) {
//            len = stringBuilder.length() / 8;
//        } else {
//            len = stringBuilder.length() / 8 + 1;
//        }
        //创建HuffmanCodes 存储压缩后的byte数组
        byte[] huffmanCodeBytes = new byte[len];
        int index = 0; //
        //每8位对应一个byte
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String stringByte;
            if (i + 8 > stringBuilder.length()) {
                //不够8位 取最后
                stringByte = stringBuilder.substring(i);
            } else {
                //够8位 每8位截取
                stringByte = stringBuilder.substring(i, i + 8);
            }
            //将stringByte转成一个byte 放到by中 parseInt(x,y) x代表需要转换的string y=2代表二进制
            huffmanCodeBytes[index] = (byte) Integer.parseInt(stringByte, 2);
            index++;
        }
        return huffmanCodeBytes;
    }

    /**
     * 重载getCode 得到哈弗曼编码
     *
     * @param root 根节点
     * @return 哈夫曼编码
     */
    public static Map<Byte, String> getCode(Node root) {
        if (root == null) {
            System.out.println("哈夫曼树为空");
        } else {
            getCodes(root.left, "0", stringBuilder);
            getCodes(root.right, "1", stringBuilder);
        }
        return huffmanCodes;
    }


    /**
     * 将传入Node的所有叶子节点的哈夫曼编码存放到huffmanCodes集合中
     *
     * @param node          传入的节点
     * @param code          节点的路径:左子节点0 右子节点:1
     * @param stringBuilder 用于拼接路径
     */
    private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        //将code加入到stringBuffer1
        stringBuilder1.append(code);
        //Node ==null
        if (node != null) {
            //判断当前节点是叶子节点 还是非叶子节点
            if (node.data == null) { //data ==null 非叶子节点 递归到叶子
                getCodes(node.left, "0", stringBuilder1);
                getCodes(node.right, "1", stringBuilder1);
            } else {
                //找到叶子节点
                huffmanCodes.put(node.data, stringBuilder1.toString());
            }
        }
    }


    /**
     * 3.通过对象的权重数组创建哈夫曼树
     *
     * @param nodes 权重数组
     * @return 哈夫曼树的根节点
     */
    private static Node createHuffmanTreeByList(List<Node> nodes) {
        while (nodes.size() > 1) {
            //排序 小-->大
            Collections.sort(nodes);
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            //拿到最小和第二小的节点 合并成一个父节点
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            //处理已经合并过的节点 0 --1 并且把父节点 加入到集合
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);
        }
        //nodes中的最后一个节点 就是哈夫曼树的根节点
        return nodes.get(0);
    }

    /**
     * 2. 拿到每个字节出现的权重数组
     *
     * @param bytes 字节数组
     * @return 统计每个字节出现的次数
     */
    private static List<Node> getNodes(byte[] bytes) {
        List<Node> nodes = new ArrayList<>();
        //存储每个Byte出现的次数
        Map<Byte, Integer> maps = new HashMap<>();
        for (byte b : bytes) {
            //等价于下述代码 1.8的新特性 merge
            maps.merge(b, 1, Integer::sum);
//            Integer count = maps.get(b);
//            if (count == null) {
//                maps.put(b, 1);
//            } else {
//                maps.put(b, count + 1);
//            }
        }
        //把每个键值对转成Node 添加到List中
        for (Map.Entry<Byte, Integer> entry : maps.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    private static void preOrder(Node root) {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("哈夫曼树为空");
        }
    }

    static class Node implements Comparable<Node> {
        Byte data;
        int weight;
        Node left;
        Node right;

        public Node(Byte data, int weight) {
            this.data = data;
            this.weight = weight;
        }

        public Byte getData() {
            return data;
        }

        public void setData(Byte data) {
            this.data = data;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", weight=" + weight +
                    '}';
        }

        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }

        //前序遍历
        public void preOrder() {
            System.out.println(this);
            if (left != null) {
                left.preOrder();
            }
            if (right != null) {
                right.preOrder();
            }
        }
    }
}
